package leetCode.sample;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 */
public class CountSmallerSolution {

    public static void main(String[] args) {
        CountSmallerSolution smallerSolution = new CountSmallerSolution();
        //System.out.println(smallerSolution.countSmaller(new int[]{5, 2, 6, 1}));
        //System.out.println(smallerSolution.countSmaller(new int[]{5, 2, 6, 2}));
        //System.out.println(smallerSolution.countSmaller(new int[]{-1}));
        //System.out.println(smallerSolution.countSmaller(new int[]{-1, -1}));
        //System.out.println(smallerSolution.countSmaller(new int[]{2,2}));
        System.out.println(smallerSolution.countSmaller2(new int[]{26, 78, 27, 100, 33, 67, 90, 23, 66, 5, 38, 7, 35, 23, 52, 22, 83, 51, 98, 69, 81, 32, 78, 28, 94, 13, 2, 97, 3, 76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41}));
    }

    public List<Integer> countSmaller(int[] nums) {
        int[] sort = new int[nums.length];
        int sortSize = 1;
        List<Integer> res = new ArrayList<Integer>(Arrays.asList(new Integer[nums.length]));
        for (int i = nums.length - 1; i >= 0; i--) {
            int curr = nums[i];
            sort[sortSize - 1] = Integer.MIN_VALUE;
            for (int j = sortSize - 1; j >= 0; j--) {
                //TODO 改为二分法会更快
                if (sort[j] >= curr) {
                    sort[j + 1] = sort[j];
                }
                if (j == 0 || sort[j - 1] < curr) {
                    sort[j] = curr;
                    res.set(i, j);
                    break;
                }
            }
            sortSize++;
        }
        return res;
    }

    private int[] index;
    private int[] helper;
    private int[] count;

    public List<Integer> countSmaller2(int[] nums) {
        List<Integer> res = new ArrayList<>(nums.length);

        index = new int[nums.length];
        helper = new int[nums.length];
        count = new int[nums.length];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }

        merge(nums, 0, nums.length - 1);

        for (int i = 0; i < count.length; i++) {
            res.add(i, count[i]);
        }
        return res;
    }

    private void merge(int[] nums, int s, int e) {
        if (s == e || s > e) return;
        int mid = (s + e) >> 1;

        if (s < mid) {
            merge(nums, s, mid);
        }

        if (mid + 1 < e) {
            merge(nums, mid + 1, e);
        }

        int i = s, j = mid + 1;
        int hi = s;
        while (i <= mid && j <= e) {
            if (nums[index[i]] <= nums[index[j]]) {
                // 右侧出
                helper[hi++] = index[j++];
            } else {
                // 左侧出 计数
                count[index[i]] += e - j + 1;
                helper[hi++] = index[i++];
            }
        }

        while (i <= mid) {
            //左侧出
            helper[hi++] = index[i++];
        }

        while (j <= e) {
            // 右侧出
            helper[hi++] = index[j++];
        }

        for (int k = s; k <= e; k++) {
            index[k] = helper[k];
        }
    }



}
